package q930_numSubarraysWithSum;

import java.util.HashMap;
import java.util.Map;

public class Solution_1 {
    /*
    哈希表的方式解决该题：
    相对滑动窗口 这种方法比较难以理解一些
    首先我们考虑 要使得一个子数组的和恰好为goal 对于恰好这个条件 我们就可以转换成前缀和的形式来计算
    在nums已经提供的情况下将其原地转换为前缀和数组
    此时 一个子数组的和恰好是goal就代表着  sum[j] - sum[i] = goal j >= i
    也就是i -> j的这一段数组之和就是goal 达到了子数组的和为goal的条件
    接下来就是如何将其转换为使用哈希表的方式来解决该题：
    先考虑题中的条件 数组中只有0和1 所以 一般来说 我们设立一个goal
    当指针不断后移的时候 sum是一个单调递增的数组 直到某一个指针开始 此时恰好有sum[p] = goal
    此时就可以开始增加ans

    那么对于map.put(nums[i] + goal, map.getOrDefault(nums[i] + goal, 0) + 1);
    可以理解为 当我么到达nums[i]的时候 此时数组的前缀和就是nums[i] 那么如果我们期望在接下来的某一处
    有 sum[j] -> sum[i]这一段可以组成一个符合要求的数组 所以我们可以记录nums[i] + goal到map中
    当到某一处j发现map中已经有nums[i] + goal 也就代表 i - j这一段是符合要求的数组

    而map中的value 就是对于num[i] + goal 有多少个数组 期望 在j处能够满足条件
    例如 1 0 1 0 1 goal = 2 转化后 为 1 1 2 2 3
    我们考虑到达2的时候 此时map被更新添加了(3, 1) 然后更新 (3, 2) 就代表从第三个数开始 期望在某个位置出现一个前缀和为3的数
    然后到第四个数 也是期望能够在某个位置出现一个前缀和为3的数 所以要更新value
     */
    public int numSubarraysWithSum(int[] nums, int goal) {
        int ans = 0;
        for (int i = 1; i < nums.length; i++) nums[i] += nums[i - 1];

        Map<Integer, Integer> map = new HashMap<>();
        map.put(goal, 1);

        for (int i = 0; i < nums.length; i++) {
            ans += map.getOrDefault(nums[i], 0);
            map.put(nums[i] + goal, map.getOrDefault(nums[i] + goal, 0) + 1);
        }
        return ans;
    }
}
